/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-17
 * Time: 8:49
 */
//673.最长递增子序列的个数
class Solution3 {
    public int findNumberOfLIS(int[] nums) {
        //1.创建dp表
        int n = nums.length;
        //len[i]以i下标结尾所有子序列中最长递增子序列的长度
        //count[i]以i下标结尾所有子序列中最长递增子序列的个数
        int[] len = new int[n];
        int[] count = new int[n];
        //2.初始化
        for(int i = 0; i < n; i++) {
            len[i] = 1;
            count[i] = 1;
        }
        int retcount = 1,retlen = 1;
        //3.状态转移
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(nums[j] < nums[i]) {
                    if(len[j]+1 == len[i]) {
                        count[i] += count[j];
                    }else if(len[j]+1 > len[i]) {
                        len[i] = len[j]+1;
                        count[i] = count[j];
                    }
                }
            }
            if(retlen == len[i]) {
                retcount += count[i];
            }else if(retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }
        //4.填表顺序
        //5.返回值
        return retcount;
    }
}
